package com.tgy.leetcode;

import java.util.*;

public class _264_丑数_II {

    public static int nthUglyNumber(int n) {

        int[] bases = {2,3,5};

        Set<Long> all = new HashSet<>();
        all.add(1L);
        PriorityQueue<Long> minHeap = new PriorityQueue<>();
        minHeap.offer(1L);

        int retVal = 0;
        for (int i = 0; i < n; i++) {

            long val = minHeap.poll();
            retVal = (int) val;
            for (int basis : bases) {

                long newVal = basis * val;

                if (all.add(newVal)) {
                    minHeap.offer(newVal);
                }
            }
        }

        return retVal;
    }

    public static void main(String[] args) {

        System.out.println(nthUglyNumber(10));
    }
}
